package com.cyh.pangu.offer;

import java.util.HashMap;
import java.util.Map;

/**
 * @author cuiyh9
 * @date 2020/8/27
 */
public class Offer10 {
    // 当n很大的时候可能会出现数字溢出，所以我们需要用结果对1000000007求余，但实际上可能还没有执行到最后一步就已经溢出了，所以我们需要对每一步的计算都要对1000000007求余
    int constant = 1000000007;
    Map<Integer, Integer> totalMap = new HashMap<>();
    public int fib(int n) {
        if (n < 2) {
            return n;
        }
        Integer value = totalMap.get(n);
        if (value == null) {
            Integer first = fib(n - 1) % constant;
            totalMap.put(n-1, first);
            Integer second =  fib(n - 2) % constant;
            totalMap.put(n-2, second);
            value =  (first +second) % constant;
            totalMap.put(n, value);
            return value;
        } else {
            return value;
        }
    }

    public static void main(String[] args) {
        Offer10 offer = new Offer10();
        int total = offer.fib(6);
        System.out.println("total:" + total);
    }
}
